//
// Created by gyc on 2023/4/25.
//
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

#include "../../common.h"

class Solution {
public:
    vector<int> findMode(TreeNode* root) {

        vector<int> res{};
        TreeNode* last = nullptr;
        int num, maxNum = 0;

        stack<TreeNode*> s1{};

        TreeNode* curr = root;

        while (curr != nullptr || !s1.empty()) {

            while (curr != nullptr) {
                s1.emplace(curr);
                curr = curr->left;
            }
            curr = s1.top();
            s1.pop();
            if (last == nullptr) {
                last = curr;
                num = 1;
            } else {
                if (curr->val == last->val) {
                    num++;
                } else {

                    if (num > maxNum) {
                        while (!res.empty()) {
                            res.pop_back();
                        }
                        res.emplace_back(last->val);
                        maxNum = num;
                    } else if (num == maxNum) {
                        res.emplace_back(last->val);
                    }
                    last = curr;
                    num = 1;
                }
            }
            curr = curr->right;
        }
        if (num > maxNum) {
            while (!res.empty()) {
                res.clear();
            }
            res.emplace_back(last->val);
            maxNum = num;
        } else if (num == maxNum) {
            res.emplace_back(last->val);
        }
        return res;
    }
};